package com.lihepeng.leecode.tree;

import org.junit.Test;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 二叉树序列化
 * 2021年6月30日09:43:51
 * 每日一题
 *
 */
public class Codec {
    // Encodes a tree to a single string.
    // 使用二叉树先序遍历 遍历树结构
    public String serialize(TreeNode root) {
        return reserialize(root,"");
    }

    private String reserialize(TreeNode root, String s) {
        if (root == null){
            s+="None,";
        }else {
            s+=s.valueOf(root.val)+",";
            s+=reserialize(root.left,s);
            s+=reserialize(root.right,s);
        }
        return s;

    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] dataArray = data.split(",");
        List<String> dataList = new LinkedList<>(Arrays.asList(dataArray));
        return rdeserialize(dataList);
    }
    private TreeNode rdeserialize(List<String>dataList){
        if (dataList.get(0).equals("None")){
            dataList.remove(0);
            return null;
        }
        // 遍历 重构树
        TreeNode treeNode = new TreeNode(Integer.parseInt(dataList.get(0)));
        dataList.remove(0);
        treeNode.left = rdeserialize(dataList);
        treeNode.right = rdeserialize(dataList);
        return treeNode;
    }
    @Test
    public void runTest(){
        TreeNode treeNode = new TreeNode(0);
        TreeNode l1 = new TreeNode(1);
        TreeNode r1 = new TreeNode(2);
        TreeNode l2 = new TreeNode(3);
        TreeNode r2 = new TreeNode(4);
        treeNode.left = l1;
        treeNode.right = r1;
        l1.left = l2;
        l1.right = r2;
        String serialize = serialize(treeNode);
        System.out.println(serialize);
    }
}
